#include <stdio.h>
#include <stdlib.h>
#define ElemType int
typedef struct {
    ElemType *data;
    int length;
}SSTable;

//顺序查找函数（使用哨兵法）
int Search_Seq(SSTable ST,ElemType key){
    ST.data[0]=key;//
    int i;
    for(i;i<ST.length;i++){
        if(key==ST.data[i])return i;
    }
}
//二分法（使用哨兵法）
int Search_Bin(SSTable ST,ElemType key){
    int low=1;
    int high=ST.length-1;
    int mid =(low+high)/2;
    int i;
    while(low<=high){
        mid=(low+high)/2;
        if(key==ST.data[mid]){
            return mid;
        }else if (key>ST.data[mid])
        {
            /* code */
            low=mid+1;
        }else{
            high=mid-1;
        }
        
    }
    return mid;
}
// 假设SqList的结构体定义如下：
typedef struct {
    int key;
    // 其他成员，如：
    // char name[20];
    // int value;
} Elem;

typedef struct {
    Elem r[100];  // 
    int length;       // 有效元素个数
} SqList;

// 修正：完整复制结构体
void InsertSort(SqList* L) {
    int i, j;
    for (i = 2; i <= L->length; i++) {
        if (L->r[i].key < L->r[i-1].key) {
            L->r[0] = L->r[i];  // 哨兵暂存整个结构体
            while(j>=0 && L->r[0].key>L->r[j].key){
                L->r[j + 1] = L->r[j];  // 整体后移结构体
                j--;
            }
            L->r[j + 1] = L->r[0];  // 插入整个结构体
        }
    }
}
//冒泡排序（无哨兵）length为个数
void BubbleSort(SqList* L){
    int i,j;
    Elem* temp;
    for(i=0;i<L->length;i++){
        
        for(j=0;j<L->length-i;j++){
            if(L->r[j].key>L->r[j+1].key){
                *temp=L->r[j+1];
                L->r[j+1]=L->r[j];
                L->r[j]=*temp;
            }
        }
    }
}
//快速排序的分离函数
int Partition(SqList* L,int low,int high){
    //枢轴结构体
    Elem*pivokey;
    *pivokey=L->r[low];
    //
    while(low<high){
        //右找小于枢轴的
        while(low<high && L->r[high].key>=pivokey->key){
            high--;
        }
        L->r[low]=L->r[high];
        //左边找大于枢轴的
        while(low<high && L->r[low].key<=pivokey->key){
            low++;
        }
        L->r[high]=L->r[low];
    }
    //枢轴元素放到对的位置
    L->r[low]=*pivokey;
    return low;
}
//快速排序
void quicklysort(SqList* L,int low,int high){
    if(low<high){
        int pivokey=Partition(L,low,high);
      //左边
        quicklysort(L,low,pivokey-1);
        //右边
        quicklysort(L,pivokey+1,high);
    }
}

//交换元素
void sswap(SqList* L,int i,int j){
    Elem temp;
    temp=L->r[i];
    L->r[i]=L->r[j];
    L->r[j]=temp;
}
//找最小值的下标
int SelectMinKey(SqList* L,int low,int high){
    int minindex=low;
    for(int i=low+1;i<=high;i++){
        if(L->r[i].key<L->r[minindex].key){
            minindex=i;
        }

    }
    return minindex;
}
//简单选择排序（无哨兵）
void choose(SqList* L) {
    int i, j;  //  记录每轮最小元素的下标

    // 外层循环：待排序区间的起始位置（从1开始，到length-1结束）
    for (i = 0; i < L->length; i++) {
         // 假设当前位置是待排序区间的最小元素

        // 内层循环：在待排序区间（i到length）中找最小元素
        j=SelectMinKey(L,i,L->length);

        // 将最小元素与待排序区间的第一个元素交换
        if (j != i) {  // 若最小元素不是当前位置，才交换
            sswap(L,i,j);
        }
    }
}

